package com.chengqs.leetcode.hot100;

import com.chengqs.leetcode.utils.DataGeneratorUtil;
import com.chengqs.leetcode.utils.TimeCostUtil;

/**
 * 双指针<br>
 * 数组、双指针<br>
 * 简单
 *
 * <H1>283. 移动零</H1>
 *
 * <P>给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。</P>
 *
 * <P>请注意 ，必须在不复制数组的情况下原地对数组进行操作。</P>
 */
public class B04MoveZeroes {
    public static void main(String[] args) {
        B04MoveZeroes moveZeroes = new B04MoveZeroes();

        int[] nums = {0, 1, 0, 3, 12};
        System.out.println("基础数据");
        TimeCostUtil.timeCost("双指针_我的方法", () -> moveZeroes.solution1_mine(nums));
        TimeCostUtil.timeCost("双指针", () -> moveZeroes.solution1(nums));

        int[] nums2 = DataGeneratorUtil.generateRandomIntArray(100000000, 0, 100000000);
        System.out.println("大数据量");
        TimeCostUtil.timeCost("双指针_两次遍历_我的方法", () -> moveZeroes.solution2_mine(nums2));
        TimeCostUtil.timeCost("双指针_一次遍历_我的方法", () -> moveZeroes.solution1_mine(nums2));
        TimeCostUtil.timeCost("双指针_一次遍历", () -> moveZeroes.solution1(nums2));
    }

    /**
     * 双指针_两次遍历
     * 相较于用swap方法，这里赋值操作只需要一次，而swap方法需要三次赋值，所以速度提升很多
     * @param nums
     */
    public void solution2_mine(int[] nums) {
        int n = 0, z = 0;
        //第一次遍历的时候，n指针记录非0的个数，只要是非0的统统都赋给nums[n]
        while (z < nums.length) {
            if (nums[z] != 0) {
                nums[n] = nums[z];
                n++;
            }
            z++;
        }
        //非0元素统计完了，剩下的都是0了
        //所以第二次遍历把末尾的元素都赋为0即可
        while (n < nums.length) {
            nums[n] = 0;
            n++;
        }
    }

    /**
     * n：number 非0的数字指针
     * z：zero 0的数字指针
     * @param nums
     */
    public void solution1_mine(int[] nums) {
        int n = 0, z = 0;
        while(z < nums.length) {
            if (nums[z] != 0) {
                // 如果非0的数字指针和0的数字指针相等，则交换
                swap(nums, n, z);
                // 交换完之后，非0的数字指针要向后移动
                n++;
            }
            // 0 的指针要不断地向后移动
            z++;
        }
    }

    // 双指针_一次遍历
    public void solution1(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
